﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    internal class InsertSort
    {
        /// <summary>
        /// 插入排序，原地排序，时间复杂度为n^2
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public static void InsertSortArray<T>(T[] array) where T : IComparable<T>
        {
            int length = array.Length;
            for (int i = 1; i < length; i++)
            {
                T currentNum = array[i];
                int j = i - 1;
                while (j >= 0 && array[j].CompareTo(currentNum) > 0)
                {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = currentNum;
            }

            return;
        }
    }
}
